package LeetCode;

public class LC_546_RemoveBoxes {

    public static void main(String[] args) {

    }

    class Solution {

        public int removeBoxes(int[] boxes) {
            int n = boxes.length;
            if (n == 0) return 0;
            int[][][] dp = new int[n][n][n];
            for (int i = 0; i < n; i++)
                for (int k = 0; k <= i; k++)
                    dp[i][i][k] = (1 + k) * (1 + k);
            for (int d = 1; d < n; d++)
                for (int r = d; r < n; r++) {
                    int l = r - d;
                    for (int k = 0; k <= l; k++) {
                        int ret = (k + 1) * (k + 1) + dp[l + 1][r][0];
                        for (int m = l + 1; m <= r; m++)
                            if (boxes[m] == boxes[l])
                                ret = Math.max(ret, dp[l + 1][m - 1][0] + dp[m][r][k + 1]);
                        dp[l][r][k] = ret;
                    }
                }
            return dp[0][n - 1][0];
        }

    }


    public class Solution_2 {

        public int removeBoxes(int[] boxes) {
            int len = boxes.length;
            if (len == 0) return 0;
            int[][][] dp = new int[len][len][len + 1];
            for (int inter = 0; inter < len; inter++) {
                for (int i = 0; i + inter < len; i++) {
                    for (int k = 0; k < len; k++) {
                        int j = i + inter;
                        dp[i][j][k] = 0;
                        if (i == j) {
                            dp[i][j][k] = (k + 1) * (k + 1);
                            continue;
                        }
                        if (dp[i + 1][j][0] + (k + 1) * (k + 1) > dp[i][j][k]) {
                            dp[i][j][k] = dp[i + 1][j][0] + (k + 1) * (k + 1);
                        }
                        for (int h = i + 1; h <= j; h++) {
                            if (boxes[h] == boxes[i]) {
                                if (dp[i + 1][h - 1][0] + dp[h][j][k + 1] > dp[i][j][k]) {
                                    dp[i][j][k] = dp[i + 1][h - 1][0] + dp[h][j][k + 1];
                                }
                            }
                        }
                    }
                }
            }
            return dp[0][len - 1][0];
        }

    }
}